package main

import . "local/algorithm/util"

/*
*

	二叉树的节点pq的最近公共祖先

解析:

		最近的意思即符合条件的深度最大的节点，也意味着我们需要通过dfs方式由下向上回溯(需要拿到左右子节点结果，走后序遍历回溯)
		回溯时有
			如果root等于p\q那么意味着该节点就是最近公共祖先，直接返回至上一层
			如果root==nil表示到达最深度也没有找到pq，返回nil至上一层
			如果root有值但是不等于pq，那么在root左子树及右子树中查找，
				如果left,right左右子树中都找到p或q，则root就是最近公共祖先，返回root至上一层
	            如果在left中找到，right中未找到，则最近公共祖先为left中回溯返回的节点，返回left至上一层
				如果在right中找到，left中未找到，则最近公共祖先为right中回溯返回的节点，返回right至上一层

		返回值: 返回值不为nil表示找到了p或q(至少有一个)，返回值为nil表示什么都没找到

		额外思考:
			二叉树回溯: 使用后序遍历，从下往上遍历整棵树
			![](http://cdn.bsummer.cn/20211125094116.png)

网友解释
张三: 我觉得吧。这就是一个后序遍历的模型，只不过是每个父节点都会接收子节点的状态（是否含有p、q）并把这个状态往上传递，直到该结点满足祖先节点的条件。这样一想就豁然开朗了。

网友题解
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/comments/1020744
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	//递归返回的条件
	if root == q || root == p {
		return root
	}

	if root == nil {
		return nil
	}

	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root
	} else if left == nil {
		return right
	} else {
		return left
	}
}
